<!DOCTYPE html>
<html>
  <head>
    <meta charset='utf-8'>

    <link rel="stylesheet" type="text/css" 
      href="/assets/css/straybirds.css" media="screen" />
    <link rel="stylesheet" type="text/css" 
      href="/assets/css/pygments.css" media="screen" />

    <!-- MathJax Section Start -->

    <script type="text/javascript"
    src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
    </script>
    <script>
        MathJax.Hub.Config({
              tex2jax: {
              skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
              }
        });
        MathJax.Hub.Queue(function() {
            var all = MathJax.Hub.getAllJax(), i;
            for(i=0; i < all.length; i += 1) {
                all[i].SourceElement().parentNode.className += ' has-jax';
            }
        });
    </script>

    <!-- MathJax Section End -->

    <!-- Google Analytics Start-->
    <script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

  ga('create', 'UA-48100787-1', 'minixalpha.github.io');
  ga('send', 'pageview');

</script>

    <!-- Google Analytics End -->

    <title>OpenJDK 源码阅读之 LinkedList</title>
  </head>

  <body>
    <div class="container">
      <header>
        <div class="container">
          <h1>
              <a href="/" title="Home Page"> 潇湘夜雨 </a>
          <span class="github-src">
            <a href ="https://github.com/minixalpha/minixalpha.github.io"
               target="_blank"
               title="Fork me on GitHub">
              <img src="/assets/images/GitHub-Mark-Light-32px.png" alt="">
            </a>
          </span>
          </h1>
        </div>
      </header>

      <aside id="left-side">
        <h2> 分类 </h2>
  <ul class="category-list">
      
            
                <li>
                <a href="/categories/源代码阅读"> 源代码阅读 (20) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/设计模式"> 设计模式 (3) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/科研"> 科研 (6) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/思想"> 思想 (2) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/技术"> 技术 (18) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/工具"> 工具 (4) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/虚拟机"> 虚拟机 (1) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/java"> java (11) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/c语言"> c语言 (4) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/读书"> 读书 (1) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/操作系统"> 操作系统 (1) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/英语"> 英语 (10) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/计算机系统"> 计算机系统 (3) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/生活"> 生活 (1) </a>
                </li>
            
      
  </ul>

      </aside>

      <aside id="right-side">
        <h2> 归档 </h2>
  <ul class="archive-list">
    
    
    
        
        
        
        
            
            <li>
                <a href="/2014/08">
                    2014-08 (1)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/07">
                    2014-07 (5)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/05">
                    2014-05 (12)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/04">
                    2014-04 (3)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/03">
                    2014-03 (11)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/02">
                    2014-02 (6)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/01">
                    2014-01 (3)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2013/11">
                    2013-11 (10)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2013/10">
                    2013-10 (3)
                </a>
            </li>

        
        
    
        
        
        
        
            
            <li>
                <a href="/2010/09">
                    2010-09 (1)
                </a>
            </li>

        
        
    
  </ul>

      </aside>

      <article>

<h1>OpenJDK 源码阅读之 LinkedList</h1>

<hr>

<h2>概要</h2>

<ul>
<li>类继承关系</li>
</ul>
<div class="highlight"><pre><code class="text language-text" data-lang="text">java.lang.Object
    java.util.AbstractCollection&lt;E&gt;
        java.util.AbstractList&lt;E&gt;
            java.util.AbstractSequentialList&lt;E&gt;
                java.util.LinkedList&lt;E&gt;
</code></pre></div>
<ul>
<li>定义</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="kd">public</span> <span class="kd">class</span> <span class="nc">LinkedList</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span>
    <span class="kd">extends</span> <span class="n">AbstractSequentialList</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span>
    <span class="kd">implements</span> <span class="n">List</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;,</span> <span class="n">Deque</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;,</span> <span class="n">Cloneable</span><span class="o">,</span> <span class="n">java</span><span class="o">.</span><span class="na">io</span><span class="o">.</span><span class="na">Serializable</span>
<span class="o">{</span>
<span class="o">}</span>
</code></pre></div>
<ul>
<li>要点</li>
</ul>

<ol>
<li>双链表</li>
<li>非同步</li>
<li>fail-fast: 即创建 iterator 后，对链表进行了添加，删除，但是却没有用 iterator 的方法，就会抛出 ConcurrentModificationException 异常。</li>
</ol>

<h2>实现</h2>

<ul>
<li>Node</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="kd">private</span> <span class="kd">static</span> <span class="kd">class</span> <span class="nc">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="o">{</span>
    <span class="n">E</span> <span class="n">item</span><span class="o">;</span>
    <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">next</span><span class="o">;</span>
    <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">prev</span><span class="o">;</span>

    <span class="n">Node</span><span class="o">(</span><span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">prev</span><span class="o">,</span> <span class="n">E</span> <span class="n">element</span><span class="o">,</span> <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">next</span><span class="o">)</span> <span class="o">{</span>
        <span class="k">this</span><span class="o">.</span><span class="na">item</span> <span class="o">=</span> <span class="n">element</span><span class="o">;</span>
        <span class="k">this</span><span class="o">.</span><span class="na">next</span> <span class="o">=</span> <span class="n">next</span><span class="o">;</span>
        <span class="k">this</span><span class="o">.</span><span class="na">prev</span> <span class="o">=</span> <span class="n">prev</span><span class="o">;</span>
    <span class="o">}</span>
<span class="o">}</span>
</code></pre></div>
<p>双链表每个结点由 <code>Node</code> 类表示, 由其成员可以看出，确实是一个双链表。</p>

<ul>
<li>add</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="cm">/**</span>
<span class="cm"> * Appends the specified element to the end of this list.</span>
<span class="cm"> *</span>
<span class="cm"> * &lt;p&gt;This method is equivalent to {@link #addLast}.</span>
<span class="cm"> *</span>
<span class="cm"> * @param e element to be appended to this list</span>
<span class="cm"> * @return {@code true} (as specified by {@link Collection#add})</span>
<span class="cm"> */</span>
<span class="kd">public</span> <span class="kt">boolean</span> <span class="nf">add</span><span class="o">(</span><span class="n">E</span> <span class="n">e</span><span class="o">)</span> <span class="o">{</span>
    <span class="n">linkLast</span><span class="o">(</span><span class="n">e</span><span class="o">);</span>
    <span class="k">return</span> <span class="kc">true</span><span class="o">;</span>
<span class="o">}</span>
</code></pre></div>
<p><code>add</code> 操作会在表的最后添加一个元素，调用 <code>linkLast</code> 实现。</p>

<ul>
<li>LinkLast</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java"><span class="kt">void</span> <span class="nf">linkLast</span><span class="o">(</span><span class="n">E</span> <span class="n">e</span><span class="o">)</span> <span class="o">{</span>
    <span class="kd">final</span> <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">l</span> <span class="o">=</span> <span class="n">last</span><span class="o">;</span>
    <span class="kd">final</span> <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">newNode</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Node</span><span class="o">&lt;&gt;(</span><span class="n">l</span><span class="o">,</span> <span class="n">e</span><span class="o">,</span> <span class="kc">null</span><span class="o">);</span>
    <span class="n">last</span> <span class="o">=</span> <span class="n">newNode</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">l</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span>
        <span class="n">first</span> <span class="o">=</span> <span class="n">newNode</span><span class="o">;</span>
    <span class="k">else</span>
        <span class="n">l</span><span class="o">.</span><span class="na">next</span> <span class="o">=</span> <span class="n">newNode</span><span class="o">;</span>
    <span class="n">size</span><span class="o">++;</span>
    <span class="n">modCount</span><span class="o">++;</span>
<span class="o">}</span>
</code></pre></div>
<p><code>linkLast</code> 先生成新的结点，再将原来的最后结点的 <code>next</code> 指向新结点，需要注意链表为空时的情况。另外，新结点的 <code>prev</code>, <code>next</code> 都是在其构造函数中设置的，所以需要将其相邻结点传入。构造函数为：</p>
<div class="highlight"><pre><code class="java language-java" data-lang="java">   <span class="kd">private</span> <span class="kd">static</span> <span class="kd">class</span> <span class="nc">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="o">{</span>
        <span class="n">E</span> <span class="n">item</span><span class="o">;</span>
        <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">next</span><span class="o">;</span>
        <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">prev</span><span class="o">;</span>

        <span class="n">Node</span><span class="o">(</span><span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">prev</span><span class="o">,</span> <span class="n">E</span> <span class="n">element</span><span class="o">,</span> <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">next</span><span class="o">)</span> <span class="o">{</span>
            <span class="k">this</span><span class="o">.</span><span class="na">item</span> <span class="o">=</span> <span class="n">element</span><span class="o">;</span>
            <span class="k">this</span><span class="o">.</span><span class="na">next</span> <span class="o">=</span> <span class="n">next</span><span class="o">;</span>
            <span class="k">this</span><span class="o">.</span><span class="na">prev</span> <span class="o">=</span> <span class="n">prev</span><span class="o">;</span>
        <span class="o">}</span>
    <span class="o">}</span>
</code></pre></div>
<ul>
<li>serialVersionUID</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java">    <span class="kd">private</span> <span class="kd">static</span> <span class="kd">final</span> <span class="kt">long</span> <span class="n">serialVersionUID</span> <span class="o">=</span> <span class="mi">876323262645176354L</span><span class="o">;</span>
</code></pre></div>
<p>序列化版本号，如果前一版本序列化后，后一版本发生了很大改变，就使用这个号告诉虚拟机，不能反序列化了。</p>

<ul>
<li>writeObject</li>
</ul>

<p>比例一下 <code>ArrayList</code> 与 <code>LinkedList</code> 中的 writeObject</p>
<div class="highlight"><pre><code class="java language-java" data-lang="java">    <span class="kd">private</span> <span class="kt">void</span> <span class="nf">writeObject</span><span class="o">(</span><span class="n">java</span><span class="o">.</span><span class="na">io</span><span class="o">.</span><span class="na">ObjectOutputStream</span> <span class="n">s</span><span class="o">)</span>
        <span class="kd">throws</span> <span class="n">java</span><span class="o">.</span><span class="na">io</span><span class="o">.</span><span class="na">IOException</span><span class="o">{</span>
        <span class="c1">// Write out element count, and any hidden stuff</span>
        <span class="kt">int</span> <span class="n">expectedModCount</span> <span class="o">=</span> <span class="n">modCount</span><span class="o">;</span>
        <span class="n">s</span><span class="o">.</span><span class="na">defaultWriteObject</span><span class="o">();</span>

        <span class="c1">// Write out array length</span>
        <span class="n">s</span><span class="o">.</span><span class="na">writeInt</span><span class="o">(</span><span class="n">elementData</span><span class="o">.</span><span class="na">length</span><span class="o">);</span>

        <span class="c1">// Write out all elements in the proper order.</span>
        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="o">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">size</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span>
            <span class="n">s</span><span class="o">.</span><span class="na">writeObject</span><span class="o">(</span><span class="n">elementData</span><span class="o">[</span><span class="n">i</span><span class="o">]);</span>

        <span class="k">if</span> <span class="o">(</span><span class="n">modCount</span> <span class="o">!=</span> <span class="n">expectedModCount</span><span class="o">)</span> <span class="o">{</span>
            <span class="k">throw</span> <span class="k">new</span> <span class="nf">ConcurrentModificationException</span><span class="o">();</span>
        <span class="o">}</span>

    <span class="o">}</span>
</code></pre></div><div class="highlight"><pre><code class="java language-java" data-lang="java">    <span class="kd">private</span> <span class="kt">void</span> <span class="nf">writeObject</span><span class="o">(</span><span class="n">java</span><span class="o">.</span><span class="na">io</span><span class="o">.</span><span class="na">ObjectOutputStream</span> <span class="n">s</span><span class="o">)</span>
        <span class="kd">throws</span> <span class="n">java</span><span class="o">.</span><span class="na">io</span><span class="o">.</span><span class="na">IOException</span> <span class="o">{</span>
        <span class="c1">// Write out any hidden serialization magic</span>
        <span class="n">s</span><span class="o">.</span><span class="na">defaultWriteObject</span><span class="o">();</span>

        <span class="c1">// Write out size</span>
        <span class="n">s</span><span class="o">.</span><span class="na">writeInt</span><span class="o">(</span><span class="n">size</span><span class="o">);</span>

        <span class="c1">// Write out all elements in the proper order.</span>
        <span class="k">for</span> <span class="o">(</span><span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">x</span> <span class="o">=</span> <span class="n">first</span><span class="o">;</span> <span class="n">x</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">;</span> <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">.</span><span class="na">next</span><span class="o">)</span>
            <span class="n">s</span><span class="o">.</span><span class="na">writeObject</span><span class="o">(</span><span class="n">x</span><span class="o">.</span><span class="na">item</span><span class="o">);</span>
    <span class="o">}</span>
</code></pre></div>
<p>注意后者没有检查　<code>modCount</code>，这是为什么呢？之前看 <code>ArrayList</code>的时候觉得是为线程安全考虑的，可是现在为什么又不检查了呢？虽然两个文件的注释中都说到，如果有多个线程操作此数据结构，应该从外部进行同步。但是一个检查，一个不检查是几个意思呀？</p>

<ul>
<li>维护数据结构一致性</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java">    <span class="kd">private</span> <span class="kt">void</span> <span class="nf">linkFirst</span><span class="o">(</span><span class="n">E</span> <span class="n">e</span><span class="o">)</span> <span class="o">{</span>
        <span class="kd">final</span> <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">f</span> <span class="o">=</span> <span class="n">first</span><span class="o">;</span>
        <span class="kd">final</span> <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">newNode</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Node</span><span class="o">&lt;&gt;(</span><span class="kc">null</span><span class="o">,</span> <span class="n">e</span><span class="o">,</span> <span class="n">f</span><span class="o">);</span>
        <span class="n">first</span> <span class="o">=</span> <span class="n">newNode</span><span class="o">;</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">f</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span>
            <span class="n">last</span> <span class="o">=</span> <span class="n">newNode</span><span class="o">;</span>
        <span class="k">else</span>
            <span class="n">f</span><span class="o">.</span><span class="na">prev</span> <span class="o">=</span> <span class="n">newNode</span><span class="o">;</span>
        <span class="n">size</span><span class="o">++;</span>
        <span class="n">modCount</span><span class="o">++;</span>
    <span class="o">}</span>
</code></pre></div>
<p>注意代码第 <code>5</code>行对 <code>f</code> 的检查，<code>6</code> 行对 <code>last</code> 的调整。一定要细心，保证操作后， <code>所有可能</code> 涉及的数据都得到相应更新。</p>

<ul>
<li>隐藏实现</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java">    <span class="kd">public</span> <span class="n">E</span> <span class="nf">getFirst</span><span class="o">()</span> <span class="o">{</span>
        <span class="kd">final</span> <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">f</span> <span class="o">=</span> <span class="n">first</span><span class="o">;</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">f</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span>
            <span class="k">throw</span> <span class="k">new</span> <span class="nf">NoSuchElementException</span><span class="o">();</span>
        <span class="k">return</span> <span class="n">f</span><span class="o">.</span><span class="na">item</span><span class="o">;</span>
    <span class="o">}</span>
</code></pre></div>
<p>注意返回的是数据，而不是<code>Node</code>，外部根本不需要知道 <code>Node</code> 的存在。
另外，为什么 <code>f == null</code> 要抛出异常而不是返回 <code>null</code>？</p>

<ul>
<li>为什么要分成两个函数　</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java">    <span class="kd">private</span> <span class="n">E</span> <span class="nf">unlinkFirst</span><span class="o">(</span><span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">f</span><span class="o">)</span> <span class="o">{</span>
        <span class="c1">// assert f == first &amp;&amp; f != null;</span>
        <span class="kd">final</span> <span class="n">E</span> <span class="n">element</span> <span class="o">=</span> <span class="n">f</span><span class="o">.</span><span class="na">item</span><span class="o">;</span>
        <span class="kd">final</span> <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">next</span> <span class="o">=</span> <span class="n">f</span><span class="o">.</span><span class="na">next</span><span class="o">;</span>
        <span class="n">f</span><span class="o">.</span><span class="na">item</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
        <span class="n">f</span><span class="o">.</span><span class="na">next</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span> <span class="c1">// help GC</span>
        <span class="n">first</span> <span class="o">=</span> <span class="n">next</span><span class="o">;</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">next</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span>
            <span class="n">last</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
        <span class="k">else</span>
            <span class="n">next</span><span class="o">.</span><span class="na">prev</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
        <span class="n">size</span><span class="o">--;</span>
        <span class="n">modCount</span><span class="o">++;</span>
        <span class="k">return</span> <span class="n">element</span><span class="o">;</span>
    <span class="o">}</span>

    <span class="kd">public</span> <span class="n">E</span> <span class="nf">removeFirst</span><span class="o">()</span> <span class="o">{</span>
        <span class="kd">final</span> <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">f</span> <span class="o">=</span> <span class="n">first</span><span class="o">;</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">f</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span>
            <span class="k">throw</span> <span class="k">new</span> <span class="nf">NoSuchElementException</span><span class="o">();</span>
        <span class="k">return</span> <span class="nf">unlinkFirst</span><span class="o">(</span><span class="n">f</span><span class="o">);</span>
    <span class="o">}</span>
</code></pre></div>
<p>删除操作分成两个函数，这是为什么呢？还有其它的一些操作也是这样。能想到的是其它操作可能也需要用到 <code>unlinkFirst</code>。</p>

<ul>
<li>LinkedList 中以 index 检索</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java">   <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="nf">node</span><span class="o">(</span><span class="kt">int</span> <span class="n">index</span><span class="o">)</span> <span class="o">{</span>
        <span class="c1">// assert isElementIndex(index);</span>

        <span class="k">if</span> <span class="o">(</span><span class="n">index</span> <span class="o">&lt;</span> <span class="o">(</span><span class="n">size</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="o">))</span> <span class="o">{</span>
            <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">x</span> <span class="o">=</span> <span class="n">first</span><span class="o">;</span>
            <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">index</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span>
                <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">.</span><span class="na">next</span><span class="o">;</span>
            <span class="k">return</span> <span class="n">x</span><span class="o">;</span>
        <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
            <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">x</span> <span class="o">=</span> <span class="n">last</span><span class="o">;</span>
            <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">size</span> <span class="o">-</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&gt;</span> <span class="n">index</span><span class="o">;</span> <span class="n">i</span><span class="o">--)</span>
                <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">.</span><span class="na">prev</span><span class="o">;</span>
            <span class="k">return</span> <span class="n">x</span><span class="o">;</span>
        <span class="o">}</span>
    <span class="o">}</span>
</code></pre></div>
<p>可以看出这里的小技巧，以 <code>index</code> 在前半段还是后半段，来决定是从前向后搜索，还是从后向前。</p>

<ul>
<li>代码重复问题</li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java">    <span class="kd">public</span> <span class="n">E</span> <span class="nf">getFirst</span><span class="o">()</span> <span class="o">{</span>
        <span class="kd">final</span> <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">f</span> <span class="o">=</span> <span class="n">first</span><span class="o">;</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">f</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span>
            <span class="k">throw</span> <span class="k">new</span> <span class="nf">NoSuchElementException</span><span class="o">();</span>
        <span class="k">return</span> <span class="n">f</span><span class="o">.</span><span class="na">item</span><span class="o">;</span>
    <span class="o">}</span>

    <span class="kd">public</span> <span class="n">E</span> <span class="nf">peek</span><span class="o">()</span> <span class="o">{</span>
        <span class="kd">final</span> <span class="n">Node</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="n">f</span> <span class="o">=</span> <span class="n">first</span><span class="o">;</span>
        <span class="k">return</span> <span class="o">(</span><span class="n">f</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span> <span class="o">?</span> <span class="kc">null</span> <span class="o">:</span> <span class="n">f</span><span class="o">.</span><span class="na">item</span><span class="o">;</span>
    <span class="o">}</span>
</code></pre></div>
<p>好奇这两个函数为什么会同时存在，Google到，原来是为了实现不同的接口，所以需要同时存在这两个函数，类似的情况还存在。</p>

<ul>
<li>DescendingIterator </li>
</ul>
<div class="highlight"><pre><code class="java language-java" data-lang="java">   <span class="kd">private</span> <span class="kd">class</span> <span class="nc">DescendingIterator</span> <span class="kd">implements</span> <span class="n">Iterator</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span> <span class="o">{</span>
        <span class="kd">private</span> <span class="kd">final</span> <span class="n">ListItr</span> <span class="n">itr</span> <span class="o">=</span> <span class="k">new</span> <span class="n">ListItr</span><span class="o">(</span><span class="n">size</span><span class="o">());</span>
        <span class="kd">public</span> <span class="kt">boolean</span> <span class="nf">hasNext</span><span class="o">()</span> <span class="o">{</span>
            <span class="k">return</span> <span class="n">itr</span><span class="o">.</span><span class="na">hasPrevious</span><span class="o">();</span>
        <span class="o">}</span>
        <span class="kd">public</span> <span class="n">E</span> <span class="nf">next</span><span class="o">()</span> <span class="o">{</span>
            <span class="k">return</span> <span class="n">itr</span><span class="o">.</span><span class="na">previous</span><span class="o">();</span>
        <span class="o">}</span>
        <span class="kd">public</span> <span class="kt">void</span> <span class="nf">remove</span><span class="o">()</span> <span class="o">{</span>
            <span class="n">itr</span><span class="o">.</span><span class="na">remove</span><span class="o">();</span>
        <span class="o">}</span>
    <span class="o">}</span>
</code></pre></div>
<p>这个很有意思，直接把 <code>next</code>, <code>hasNext</code>　函数设置为 <code>previous</code> 就行了，很大程度上减少了代码。</p>


      </article>

      <div class="comments">
        
          <div id="disqus_thread"></div>
 <script type="text/javascript">
     /* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */
     var disqus_shortname = 'minixalpha'; // required: replace example with your forum shortname

     /* * * DON'T EDIT BELOW THIS LINE * * */
     (function() {
         var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
         dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
         (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
     })();
 </script>
 <noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
    <a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>
    

        
      </div>


      <footer>
        Copyright (c) minixalpha 2014
      </footer>

    </div>
  </body>
</html>
